Binary Search Tree

Worst 때문에 쓸 일 없겠지만 basic 중의 basic.

struct Node {
    int key;
    Node* l;
    Node* r;

    void printInorder() {
        if (l) l->printInorder();
        printf("%d ", key);
        if (r) r->printInorder();
    }
};

Node* newNode(int key) {
    Node* ret = new Node();
    ret->key = key;
    ret->l = ret->r = 0;
    return ret;
}

struct BST {
    Node* root;
    BST() {
        root = 0;
    }
    void insert(int key) {
        if (root == 0) {
            root = newNode(key);
            return;
        }
        Node* p = root;
        Node* myNode = newNode(key);
        while(true) {
            if (p->key == key) return; // duplicate
            else if (p->key > key) {
                if (p->l == 0) {
                    p->l = myNode;
                    return;
                }
                p = p->l;
            } else {
                if (p->r == 0) {
                    p->r = myNode;
                    return;
                }
                p = p->r;
            }
        }
    }
    Node* find(int key) {
        if (root == 0) return 0;
        Node* p = root;
        while(true) {
            if (p->key == key) return p;
            else if (p->key > key) {
                if (p->l == 0) {
                    return 0;
                }
                p = p->l;
            } else {
                if (p->r == 0) {
                    return 0;
                }
                p = p->r;
            }
        }
    }
    void print() {
        if(root) root->printInorder();
        printf("\n");
    }
} bst;

Time Complexity (with Random Key)

• Insert: $O(\log N)$
• Find: $O(\log N)$